package cn.bellychang.leetcode.question844;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * @author ChangLiang
 * @date 2021/1/27
 */
public class Solution {

    public boolean backspaceCompare(String S, String T) {
        Deque<Character> stackS = new ArrayDeque<>();
        Deque<Character> stackT = new ArrayDeque<>();
        char[] charsS = S.toCharArray();
        char[] charsT = T.toCharArray();
        for (char s : charsS) {
            if (s == '#') {
                if (stackS.size() > 0) {
                    stackS.pop();
                }
            } else {
                stackS.push(s);
            }
        }
        for (char c : charsT) {
            if (c == '#') {
                if (stackT.size() > 0) {
                    stackT.pop();
                }
            } else {
                stackT.push(c);
            }
        }
        if (stackS.size() != stackT.size()) {
            return false;
        } else {
            int size = stackS.size();
            for (int i = 0; i < size; i++) {
                Character popS = stackS.pop();
                Character popT = stackT.pop();
                 if (popS != popT) {
                    return false;
                }

            }
        }
        return true;
    }
}
